FIG. 1 depicts a schematic diagram of a telecommunications network in the prior art, such as the Internet, which transports data packets from one node to another. Each endpoint, server, router, or other device that is capable of transmitting and/or receiving packets in the network is generically referred to as a “network node,” or simply “node.” A node that originates one or more packets, as part of a packet stream, is referred to as a “source node,” and a node that acts as the terminus for a packet stream is referred to as a “destination node.” For the purposes of this specification, a “network path” is defined as the physical transmission route between a pair of source and destination nodes in a network.
The service provided by a network path is characterized by its signal quality. An important aspect of signal quality is “quality of service,” which, for the purposes of this specification, is defined as a function of one or more of the bandwidth, error rate, and latency from one node to another. For the purposes of this specification, the “bandwidth” from one node to another is defined as an indication of the amount of information per unit time that can be transported from the first node to the second. Typically, bandwidth is measured in bits or bytes per second. For the purposes of this specification, the “error rate” from one node to another is defined as an indication of the amount of information that is corrupted as it travels from the first node to the second. Typically, error rate is measured in bit errors per number of bits transmitted or in packets lost per number of packets transmitted. For the purposes of this specification, the “latency” from one node to another is defined as an indication of how much time is required to transport information from one node to another. Typically, latency is measured in seconds.
In the transmission of any packet stream, there is a source node and a destination node. The two nodes can be the same type of device, such as two Voice-over-Internet-Protocol (VoIP) telephone clients, or can be different devices, such as a personal computer with a browser and a web server. Of course, the source node for one packet stream can be the destination node for another packet stream.
Some applications—for example, e-mail—are generally more tolerant of the quality of service provided by the network path, but some other applications—particularly VoIP telephony and streaming audio and video—are generally very sensitive. While some network paths provide quality-of-service guarantees, many others, including most of those through the Internet, do not. The result is that the provisioning of applications like telephony through the Internet can require transmitting some packets of a given packet stream across one network path and, as the quality of service changes, transmitting subsequent packets of the same stream across another network path, in order to maintain the required or preferred quality-of-service level. This requires evaluating the various possible network paths in a timely and efficient manner.
A technique exists of using what is referred to as a “relay node” to improve or maintain quality of service in a network that is without a quality-of-service guarantee. The relay node is positioned within the network between a source node and destination node, is addressable by the source node, and is able to relay traffic packets to the destination node. The relay node operates by forwarding certain packets received from a source node to the destination node that is specified by the source node. Relay nodes are discussed in U.S. patent application Ser. No. 11/201892, filed on Aug. 11, 2005, which is incorporated herein by reference.
One of the persistent and difficult problems in this area involves finding new relay nodes to use, quickly and efficiently, such as when the quality of service in a given path has degraded or because of a user-initiated or a network administrator-initiated change. In a first technique of the prior art, a new relay node is selected randomly. This has the advantage of being quick and of not creating excess probing traffic in the network, which can itself degrade the quality of service (QoS) of other traffic-carrying channels. This solution is disadvantageous, however, in that the random selection of a new relay node does not always yield a path through the new node with better QoS than before.
In a second technique of the prior art, a comprehensive examination of a number of randomly-selected relay nodes is conducted, followed by the selection of a path through a relay node found to have an acceptable QoS. Examining the nodes serially is typically too slow to be useful, unless an acceptable node is found early in the search. But examining the nodes in parallel typically creates enough congestion to adversely affect the QoS of other traffic-carrying channels in the network.
The need exists, therefore, for an invention that improves the evaluation of the signal qualities that are associated with multiple network paths, as well as the selection of one of those paths to handle the transmission of packets.